#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int MAXN=1e5+7;
typedef long long ll;
bool is_prime[MAXN];
int prime[MAXN], p_cnt;
int mu[MAXN];
int sum[MAXN];
void Init() {
	memset(is_prime, 1, sizeof(is_prime));
	p_cnt=0;
	mu[1]=1;
	for (int i=2; i<MAXN; ++i) {
		if (is_prime[i]) {
			prime[p_cnt++]=i;
			mu[i]=-1;
		}
		for (int j=0; j<p_cnt&&i*prime[j]<MAXN; ++j) {
			is_prime[i*prime[j]]=false;
			if (i%prime[j]==0) {
				mu[i*prime[j]]=0;
				break;
			}
			else {
				mu[i*prime[j]]=-mu[i];
			}
		}
	}
	sum[0]=0;
	for (int i=1; i<MAXN; ++i) sum[i]=sum[i-1]+mu[i];
}
ll get(ll a, ll b, ll k) {
	if (k==0) return 0;
	a=a/k; b=b/k;
	if (a==0 || b==0) return 0;
	ll last,res=0;
	if (a>b) swap(a,b);
	for (ll i=1; i<=a; i=last+1) {
		last=min(a/(a/i), b/(b/i));
		res+=(ll)(sum[last]-sum[i-1])*(ll)((2*(b/i)-(a/i)+1)*(a/i)/2);
	}
	return res;
}
int main() {
	Init();
	int a,b,c,d,k;
	int T;
	cin>>T;
	int tes=1;
	ll res;
	while (T--) {
		scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
		res=get(b,d,k)-get(a-1,d,k)-get(c-1,b,k)+get(a-1,c-1,k);
		printf("Case %d: %lld\n", tes, res);
		++tes;
	}
	return 0;
}
